/**
 * Write code to remove duplicates from an unsorted linked list.
 * <p>
 * Example1:
 * <p>
 * <p>
 * Input: [1, 2, 3, 3, 2, 1]
 * Output: [1, 2, 3]
 * <p>
 * <p>
 * Example2:
 * <p>
 * <p>
 * Input: [1, 1, 1, 1, 2]
 * Output: [1, 2]
 * <p>
 * <p>
 * Note:
 * <p>
 * <p>
 * The length of the list is within the range[0, 20000].
 * The values of the list elements are within the range [0, 20000].
 * <p>
 * <p>
 * Follow Up:
 * <p>
 * How would you solve this problem if a temporary buffer is not allowed?
 * <p>
 * Related Topics 哈希表 链表 双指针 👍 167 👎 0
 */

package com.xixi.basicAlgroithms.hash;

import com.xixi.dataStructure.lineList.ListNode;

import java.util.HashSet;
import java.util.Set;

public class ID_interview_02_01_RemoveDuplicateNodeLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_02_01_RemoveDuplicateNodeLcci().new Solution();
    }

//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeDuplicateNodes(ListNode head) {

            ListNode sentry = new ListNode();
            sentry.next = head;

            Set<Integer> nodeSet = new HashSet<>();

            ListNode nextNode = head;
            ListNode previousPointer = sentry;
            while (nextNode != null) {
                if (nodeSet.contains(nextNode.val)) {
                    nextNode = nextNode.next;
                    continue;
                } else {
                    nodeSet.add(nextNode.val);
                    previousPointer.next = nextNode;
                    previousPointer = previousPointer.next;
                    nextNode = nextNode.next;
                }

            }

            previousPointer.next = null;
            return sentry.next;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}